/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASI30/FONT#2=BASB30/FONT#10=BAXM30/FONT#11=ZERO30/FONT#12=SUB/FONT#13=GRKB30/FONT#3=STA200/FONT#4=NGB25
␈↓ ↓H␈↓␈↓βS␈↓∧ Department of Computer Science, STANFORD UNIVERSITY, Stanford, California 94305

␈↓ ↓H␈↓∧Telephone: 415 497-4430␈↓ 
⊃April 11, 1984 

␈↓ ↓H␈↓∧Electronic mail: JMC␈↓@␈↓∧SU-AI␈↓
.␈↓∧ARPA




␈↓ ↓H␈↓Dr. Stephen Wolfram
␈↓ ↓H␈↓Institute for Advanced Study
␈↓ ↓H␈↓Princeton, NJ 08540

␈↓ ↓H␈↓Dear Steve:

␈↓ ↓H␈↓        Thanks␈α∞for␈α∞your␈α∞␈↓↓Cellular␈α∂Automata:␈α∞towards␈α∞a␈α∞paradigm␈α∂for␈α∞complexity␈↓.␈α∞ I␈α∞found␈α∂it␈α∞quite
␈↓ ↓H␈↓clear␈αand␈αsome␈αof␈αthe␈αresults␈αcurious.␈α However,␈αit␈αdid␈αnot␈αrelieve␈αmy␈αprevious␈αdoubts␈αabout␈αthat
␈↓ ↓H␈↓line of research.

␈↓ ↓H␈↓        Getting␈αappropriate␈αparadigms␈αfor␈αcomplexity␈α
is␈αof␈αgreat␈αimportance.␈α It␈αseems␈α
doubtful␈αto
␈↓ ↓H␈↓me␈αthat␈αcomplexity␈αof␈α
intellect,␈αbiological␈αcomplexity␈αand␈α
the␈αcomplexities␈αassociated␈αwith␈α
physical
␈↓ ↓H␈↓phenomena like turbulence will all belong to similar paradigms.

␈↓ ↓H␈↓        Also␈α
I␈α
have␈α
considerable␈α
doubt␈α
whether␈α
cellular␈α
automata␈α
in␈α
general␈α
relate␈α
well␈α
to␈α∞any␈α
of
␈↓ ↓H␈↓these,␈αalthough␈α
they␈αare␈αmost␈α
likely␈αto␈α
relate␈αto␈αturbulence-type␈α
complexity.␈α The␈α
fact␈αthat␈αthey␈α
are
␈↓ ↓H␈↓not␈α⊂selected␈α⊂for,␈α⊂either␈α⊂naturally␈α⊂or␈α⊂by␈α⊂thinking,␈α⊂is␈α⊂the␈α⊂main␈α⊂reason.␈α⊂ In␈α⊂any␈α⊂case␈α⊂I␈α⊃have␈α⊂the
␈↓ ↓H␈↓following remarks.

␈↓ ↓H␈↓        1.␈α
Any␈α
≡nite␈α
collection␈α
␈↓
(A␈↓1␈↓
,␈α
...␈α
,A␈↓n␈↓
)␈↓␈α
of␈α
cellular␈α
automata␈α
can␈α
be␈α
superposed␈α
into␈α
a␈α
single
␈↓ ↓H␈↓automaton␈α∪␈↓
A␈↓␈α∩with␈α∪␈↓
r = max(r␈↓1␈↓
, ... ,r␈↓n␈↓
)␈↓␈α∪and␈α∩␈↓
k = k␈↓1␈↓
k␈↓2␈↓
...k␈↓n␈↓
␈↓.␈α∪ The␈α∩state␈α∪space␈α∪of␈α∩␈↓
A␈↓␈α∪is␈α∪just␈α∩an
␈↓ ↓H␈↓enumeration␈αof␈αthe␈αCartesian␈αproduct␈αof␈αthe␈αstate␈αspaces␈αof␈α␈↓
A␈↓1␈↓
, ... ,A␈↓n␈↓
␈↓,␈αand␈αthe␈α␈↓
f␈↓␈αjust␈αinvolves
␈↓ ↓H␈↓the␈α
product␈α
of␈α
the␈α
␈↓
f␈↓␈↓i␈↓'s␈α
acting␈α
independently.␈α
 A␈α
suitable␈α
notation␈α
is␈α
an␈α
exercise␈α
for␈α
anyone␈α
who
␈↓ ↓H␈↓≡nds␈α↔the␈α↔concept␈α_promising.␈α↔ Therefore,␈α↔behaviors␈α_corresponding␈α↔to␈α↔the␈α_superposition␈α↔of
␈↓ ↓H␈↓behaviors of separate automata are readily produced.

␈↓ ↓H␈↓        2.␈α∂Any␈α∞Turing␈α∂machine␈α∞is␈α∂trivially␈α∂a␈α∞cellular␈α∂automaton.␈α∞ The␈α∂state␈α∞space␈α∂of␈α∂the␈α∞cellular
␈↓ ↓H␈↓automaton␈α
is␈α
the␈α
product␈α
of␈α
three␈α
spaces␈α
-␈α
the␈α
state␈α
space␈α
of␈α
the␈α
Turing␈α
machine,␈α
the␈αsymbol␈α
space
␈↓ ↓H␈↓of␈αthe␈αTuring␈α
machine,␈αand␈αone␈α
bit␈αquantity␈αcalled␈α
the␈α␈↓
activity␈↓.␈α Corresponding␈α
to␈αa␈αstate␈α
of␈αthe
␈↓ ↓H␈↓Turing␈α
machine␈α
is␈αany␈α
state␈α
of␈α
the␈αcellular␈α
automaton␈α
in␈α
which␈αexactly␈α
one␈α
cell␈α
has␈α␈↓
activity = 1␈↓.
␈↓ ↓H␈↓The␈αlaw␈αof␈αmotion␈αof␈α
the␈αautomaton␈αspeci≡es␈αthat␈αany␈αcell␈α
of␈αthe␈αautomaton␈αsuch␈αthat␈αit␈α
and␈αits
␈↓ ↓H␈↓neighbors␈α
have␈α
␈↓
activity = 0␈↓␈α
retains␈α
its␈α
state.␈α
 The␈α∞active␈α
cell␈α
and␈α
its␈α
neighbors␈α
change␈α
state␈α∞in␈α
a
␈↓ ↓H␈↓way␈αthat␈αis␈αin␈αobvious␈αcorrespondence␈αto␈αthe␈αtable␈αof␈αthe␈αTuring␈αmachine.␈α This␈αalso␈αsettles␈αyour
␈↓ ↓H␈↓conjecture about universality.

␈↓ ↓H␈↓        3.␈αAll␈αthe␈αknown␈αpossible␈αbehaviors␈α
of␈αTuring␈αmachines␈αtherefore␈αcarry␈αover␈α
into␈αpossible
␈↓ ↓H␈↓behaviors␈αof␈αcellular␈αautomata,␈αand␈αthis␈αshows␈αthat␈αyour␈αexperimentally␈αsuggested␈αclassi≡cation␈αof
␈↓ ↓H␈↓the␈αbehaviors␈αof␈αcellular␈α
automata␈αis␈αfar␈αfrom␈α
exhaustive.␈α Although␈αstatistical␈αexperiments␈α
might
␈↓ ↓H␈↓suggest␈α⊂that␈α⊂the␈α⊂most␈α⊂cellular␈α⊂automata␈α⊃≡t␈α⊂your␈α⊂classi≡cation,␈α⊂any␈α⊂kind␈α⊂of␈α⊂natural␈α⊃or␈α⊂arti≡cial
␈↓ ↓H␈↓selection might concentrate on those that don't.
␈↓ ↓H␈↓αDr. Stephen Wolfram␈↓ ¬nApril 11, 1984␈↓ 
nPage 2␈↓ 


␈↓ ↓H␈↓        4.␈α⊂This␈α⊂suggests␈α⊂the␈α⊂invention␈α⊂of␈α⊂cellular␈α⊂automata␈α⊂exhibiting␈α⊂interesting␈α⊂behavior␈α⊂as␈α∂a
␈↓ ↓H␈↓supplement to statistical experiment.

␈↓ ↓H␈↓        5.␈αHere␈αis␈αan␈αexample␈αof␈αa␈αrealizable␈αexotic␈αbehavior.␈α Your␈αfavorite␈αcellular␈α
automaton,␈αa
␈↓ ↓H␈↓Turing␈α⊗machine␈α⊗to␈α⊗be␈α⊗described␈α⊗subsequently,␈α⊗and␈α⊗a␈α⊗third␈α⊗component␈α⊗are␈α∃approximately
␈↓ ↓H␈↓superposed.␈α The␈αTuring␈αmachine␈αlooks␈αfor␈α
a␈αcounter-example␈αto␈αFermat's␈αlast␈αtheorem.␈α
However,
␈↓ ↓H␈↓it␈αdoes␈α
so␈αwhile␈αmoving␈α
to␈αthe␈α
right␈αafter␈αeach␈α
trial␈αtuplet␈α
␈↓
(x,y,z,n)␈↓␈αso␈αthat␈α
any␈α≡nite␈α
region␈αof
␈↓ ↓H␈↓the␈αtape␈αbecomes␈αinactive␈αin␈αthat␈αcomponent␈α
as␈αlong␈αas␈αno␈αcounter-example␈αhas␈αbeen␈αfound.␈α
 The
␈↓ ↓H␈↓third␈α∞component␈α∂remains␈α∞passive␈α∞until␈α∂the␈α∞Turing␈α∂machine␈α∞activates␈α∞it␈α∂on␈α∞≡nding␈α∂the␈α∞counter-
␈↓ ↓H␈↓example.␈α
 Then␈α
it␈α
does␈α
whatever␈α
you␈α
please.␈α For␈α
example,␈α
it␈α
may␈α
wipe␈α
out␈α
the␈α
≡rst␈αcomponent,
␈↓ ↓H␈↓i.e. make its state 0, and then begin some arbitrary behavior.

␈↓ ↓H␈↓        6.␈αThe␈α
point␈αof␈α
this␈αexotic␈α
example␈αand␈α
others␈αyou␈α
might␈αconstruct␈α
is␈αthat␈αcellular␈α
automata
␈↓ ↓H␈↓are␈α∞too␈α∞general␈α∞to␈α∞give␈α∞insight␈α∞into␈α∞complexity␈α∞unless␈α∞additional␈α∞assumptions␈α∞are␈α∞made.␈α∂ If␈α∞you
␈↓ ↓H␈↓want␈αphysics,␈αyou␈αmust␈αput␈αin␈αsome␈αphysical␈αassumptions.␈α If␈αyou␈αwant␈αbiology␈αyou␈αmust␈αput␈αthat
␈↓ ↓H␈↓in,␈α∞and␈α∞if␈α∞you␈α∞want␈α∂computers␈α∞or␈α∞intellectual␈α∞life␈α∞you␈α∂must␈α∞design␈α∞them␈α∞or␈α∞make␈α∂a␈α∞"biological"
␈↓ ↓H␈↓system and wait a very long time for them to evolve.

␈↓ ↓H␈↓        7.␈α∞One␈α∞might␈α∞hope␈α∞to␈α
learn␈α∞something␈α∞by␈α∞studying␈α∞cellular␈α
automata␈α∞with␈α∞small␈α∞␈↓
k␈↓␈α∞and␈α
␈↓
r␈↓.
␈↓ ↓H␈↓However,␈α∩experience␈α∪with␈α∩similar␈α∩(1950s␈α∪and␈α∩1960s)␈α∩studies␈α∪of␈α∩Turing␈α∩machines␈α∪with␈α∩small
␈↓ ↓H␈↓numbers␈αof␈αstates␈αand␈αsymbols␈αsuggest␈αthat␈αthis␈αhope␈αis␈αrather␈αforlorn.␈α The␈αsearch␈αfor␈αuniversal
␈↓ ↓H␈↓Turing␈α∃machines␈α∀with␈α∃minimal␈α∀state-symbol␈α∃product␈α∀degenerated␈α∃into␈α∀inventing␈α∃ever␈α∀more
␈↓ ↓H␈↓complicated␈αcoding␈α
schemes␈αto␈α
prove␈αtheir␈α
universality.␈α I␈α
believe␈αthat␈α
simulation␈αexperiments␈α
also
␈↓ ↓H␈↓didn't lead to much.

␈↓ ↓H␈↓        8.␈αThe␈αnumber␈αof␈αfeedback␈αsystems␈αleading␈αto␈αchaotic␈αbehavior␈αis␈αlegion.␈α You␈αcan␈αpoint␈αa
␈↓ ↓H␈↓camera␈α
at␈α
the␈α
screen␈α
or␈α
iterate␈α
copying␈α
a␈α
pattern␈α
on␈α
a␈α
xerox␈α
machine␈α
or␈α
repeatedly␈α
copy␈α
a␈αtape
␈↓ ↓H␈↓loop␈α
onto␈α
itself.␈α
 In␈α
each␈α
case␈α
you␈α
can␈α
put␈α
some␈α
device␈α
in␈α
for␈α
transforming␈α
the␈α
signal␈α
in␈α
series␈α
with
␈↓ ↓H␈↓the␈αcopying.␈α Most␈αadjustments␈αof␈αthe␈αsystem␈αlead␈αto␈αdegenerate␈α≡xed␈αpoints,␈αbut␈αexperiment␈αcan
␈↓ ↓H␈↓≡nd patterns with considerable structure.  Display hack programs are in the same general class.

␈↓ ↓H␈↓        9.␈α
Of␈α
course␈α
the␈α
mathematical␈α
formalisms␈α
for␈α
quantifying␈α
the␈α
disorder␈α
are␈α
new␈α
and␈α
so␈αis␈α
the
␈↓ ↓H␈↓topological␈α⊃classi≡cation␈α⊃of␈α∩some␈α⊃of␈α⊃the␈α∩cases.␈α⊃ Nevertheless,␈α⊃I␈α∩still␈α⊃doubt␈α⊃that␈α∩applying␈α⊃these
␈↓ ↓H␈↓formalisms to cellular automata will by itself tell much about physics, biology or computation.

␈↓ ↓H␈↓        10.␈αCellular␈αautomaton␈αmodels␈αembodying␈αsome␈αspeci≡c␈αfeatures␈αof␈αthe␈αdomain␈αunder␈αstudy
␈↓ ↓H␈↓may be more fruitful.


␈↓ ↓H␈↓Sincerely,



␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Professor of Computer Science